perm filename START.ING[AM,DBL] blob
sn#400111 filedate 1978-12-06 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \SSEC{Heuristics Suggest New Tasks}
C00014 00003 \SSSEC{An Illustration: Discovering Primes}
C00021 00004
C00024 ENDMK
C⊗;
\SSEC{Heuristics Suggest New Tasks}
\SSSEC{An Illustration: ``Fill in Generalizations of Equality''}
\SSSEC{The Ratings Game}
\SSEC{Heuristics Create New Concepts}
\SSSEC{An Illustration: Discovering Primes}
\SSSEC{The Theory of Creating New Concepts}
\SSSEC{Another Illustration: Squaring a number}
\SSEC{Heuristics Fill in Entries for a Facet}
\SSSEC{An Illustration: ``Fill in Examples of Set-union''}
\SSSEC{Heuristics Propose New Conjectures}
\SSSEC{An Illustration: ``All primes except 2 are odd''}
\SSSEC{Another illustration: Discovering Unique Factorization}
\SSEC{Gathering Relevant Heuristics}
\SSSEC{Domain of Applicability}
\SSSEC{Rippling}
\SSSEC{Ordering the Relevant Heuristics}
\SSEC{AM's Starting Heuristics}
\SSSEC{Heuristics Grouped by the Knowledge They Embody}
\SSSEC{Heuristics Grouped by How Specific They Are}
\NSECP{CONCEPTS}
\SSEC{Motivation and Overview}
\SSSEC{A Glimpse of a Typical Concept}
\SSSEC{The main constraint: Fixed set of facets}
\SSSEC{BEINGs Representation of Knowledge}
\SSEC{Facets}
\SSSEC{Generalizations/Specializations}
\SSSEC{Examples/Isa's}
\SSSEC{In-Domain-of/In-Range-of}
\SSSEC{Views}
\SSSEC{Intuitions}
\SSSEC{Analogies}
\SSSEC{Conjec's}
\SSSEC{Definitions}
\SSSEC{Algorithms}
\SSSEC{Domain/Range}
\SSSEC{Worth}
\SSSEC{Interest}
\SSSEC{Suggest}
\SSSEC{Fill/Check}
\SSSEC{Other Facets which were Considered}
\SSEC{AM's Starting Concepts}
\SSSEC{Diagram of Initial Concepts}
\SSSEC{Summary of Initial Concepts}
\SSSEC{Rationale behind Choice of Concepts}
\NSECP{RESULTS}
\SSEC{What AM Did}
\SSSEC{Linear Task-by-task Summary of a Good Run}
\SSSEC{Two-Dimensional Behavior Graph}
\SSSEC{AM as a Computer Program}
\SSEC{Experiments with AM}
\SSSEC{Must the Worth numbers be finely tuned?}
\SSSEC{How finely tuned is the Agenda?}
\SSSEC{How valuable is tacking reasons onto each task?}
\SSSEC{What if certain concepts are eliminated/added?}
\SSSEC{Can AM work in a new domain: Plane Geometry?}
\NSECP{EVALUATING AM}
\SSEC{Judging Performance}
\SSSEC{AM's Ultimate Discoveries}
\SSSEC{The Magnitude of AM's Progress}
\SSSEC{The Quality of AM's Route}
\SSSEC{The Character of the User-System Interactions}
\SSSEC{AM's Intuitive Powers}
\SSSEC{Experiments on AM}
\SSSEC{How to Perform Experiments on AM}
\SSSEC{Future Implications of this Project}
\SSSEC{Open Problems: Suggestions for Future Research}
\SSSEC{Comparison to Other Systems}
\SSEC{Capabilities and Limitations of AM}
\SSSEC{Current Abilities}
\SSSEC{Current Limitations}
\SSSEC{Limitations of the Agenda scheme}
\SSSEC{Limiting Assumptions}
\SSSEC{Choice of Domain}
\SSSEC{Limitations of the Model of Math Research}
\SSSEC{Ultimate powers and weaknesses}
\SSEC{Final Conclusions}
\setcount4 0
\ASEC{CONCEPTS}
\ASSEC{LISP Representation}
\ASSSEC{The `Compose' Concept}
\ASSSEC{The `Osets' Concept}
\ASSECP{Concepts created by AM}
\ASSECP{Maximally-Divisible Numbers}
\ASEC{HEURISTICS}
\ASSEC{Heuristics for dealing with Anything}
\ASSEC{Heuristics for dealing with Any-concept}
\ASSSEC{Heuristics for any facet of Any-concept}
\ASSSEC{Heuristics for the Examples facets of Any-concept}
\ASSSEC{Heuristics for the Conjecs facet of Any-concept}
\ASSSEC{Heuristics for the Analogies facet of Any-concept}
\ASSSEC{Heuristics for the Genl/Spec facets of Any-concept}
\ASSSEC{Heuristics for the View facet of Any-concept}
\ASSSEC{Heuristics for the In-dom/ran-of facets of Any-concept}
\ASSSEC{Heuristics for the Definition facet of Any-concept}
\ASSEC{Heuristics for dealing with any Active concept}
\ASSEC{Heuristics for dealing with any Predicate}
\ASSEC{Heuristics for dealing with any Operation}
\ASSEC{Heuristics for dealing with any Composition}
\ASSEC{Heuristics for dealing with any Insertions}
\ASSEC{Heuristics for dealing with the operation Coalesce}
\ASSEC{Heuristics for dealing with the operation Canonize}
\ASSEC{Heuristics for dealing with the operation Substitute}
\ASSEC{Heuristics for dealing with the operation Restrict}
\ASSEC{Heuristics for dealing with the operation Invert}
\ASSEC{Heuristics for dealing with Logical combinations}
\ASSEC{Heuristics for dealing with Struc\-tures}
\ASSEC{Heuristics for dealing with Ordered-struc\-tures}
\ASSEC{Heuristics for dealing with Unordered-struc\-tures}
\ASSEC{Heuristics for dealing with Multiple-eles-struc\-tures}
\ASSEC{Heuristics for dealing with Sets}
\ASEC{TRACE}
\ASEC{BIBLIOGRAPHY}
\NNSECP{Acknowledgements}
\SSSEC{Diagram of Initial Concepts}
.B0
.TREECON: PAGE;
Anything
/ \
/ \
/ \
Any-concept \4non-concepts\0
/ \
/ \
/ \
/ \
⊂∂∂∂∂∂∂∂∂∂Activity Object
} / \ / } \
Relation / \ / } \
/ Predicate Operation Atom Conjec Structure∂∂∂∂∂∂∂∂⊃
Logical-reln / \ } } / } } }\ }
Constant-pred Equality-pred } Truth-value / } } } \ Struc-of-strucs
.ONCE TURN OFF ``\``
\ \ \ } / } Empty} \
.ONCE TURN OFF ``\``
\ \ \ ∪ / } } \
Const-T Const-F Obj-equal ∩ Mult-eles Non-mult Ord Unordered
∪ \ \ \ \ / } / /
Coalescing \ \ \ Osets }/ /
Inverted-operation \ \ \ / /
Canonization \ \ \ /} /
Composition \ \ Sets } /
Restricted-operation \ \ } /
# \ \ ∪ /
# \ \ ∩ /
\ \ ∪ /
\ Lists /
\ \ /
\ \ /
\ ∃
\ / \
Bags \
Ord-pairs
.E
The diagram above represents the ``topmost" concepts
which AM had initially,
shown connected via
Specialization links (\8\\0) and Examples links (\8α\\0).
The only concepts not diagrammed are \4examples\0 of the concept Operation.
There are 47 such operations.
Also, we should note that many entities exist in the system
which are not themselves concepts. For example, the number ``3", though it
be an \4example\0 of many concepts, is not itself a concept.
All entities which \4are\0 concepts are present on the list called
CONCEPTS, and they all have property lists (with facet names as the
properties). In hindsight, this somewhat arbitrary scheme is regrettable.
A more aesthetic designer might have come up with a more uniform system
of representation than AM's.
\SSSEC{An Illustration: Discovering Primes}
Here is a heuristic rule that
results in a new concept being created:
\han2{{\it If the current task was {\6(Fill-in examples of F)},}}
\han3{{\it and F is an operation from domain space A into range space B,}}
\han3{{\it and more than 100 items are known examples of A (in the domain of F),}}
\han3{{\it and more than 10 range items (in B) were found by applying F to these
domain items,}}
\han3{{\it and at least 1 of these range items is a distinguished member (esp:
extremum)\foo{
This is handled as follows: AM takes the given list of range items. It eliminates
any which are not interesting (according to Interests(B)) or extreme (an entry
on B.Exs-Bdy, the boundary examples of B).
Finally, all those extreme range items are moved to
the front of this list.
AM begins walking down this list, creating
new concepts according to the rule. Sooner or later,
a timer (or a storage-space-watcher) will terminate this costly activity.
Only the frontmost
few range items on the list will have generated new concepts.
So ``especially" really just means priority consideration. }
of B,}}
\han2{{\it Then (for each such distinguished member
`b'$\epsilon$B) create the following new concept:}}
\yskip
\han4{\6Name: {\it F\inv -of-b}}
\han4{\6Definition: \it $\lambda (x) \biglp F(x) = b \bigrp $}
\han4{\6Generalization: {\it A }}
\han4{\6Worth: \it $ Average \biglp Worth(A), Worth(F), Worth(B), Worth(b), $}
\han7{$100 \times max(10, \|Examples(B)\|)\bigrp $}
\han4{\6Interest: \it Any conjecture involving both this concept and either F or F\inv }
\han5{\it In case the user asks, the reason for doing this is:
``Worthwhile
investigating those A's which have an unusual F-value, namely, those
whose F-value is b"}
\yskip
\han3{\it and the total amount of time to spend
right now on all of these new
concepts is computed as: }
\han4{\it Half the remaining cpu time in the current
task's time quantum.}
\han3{\it and the total amount of space to spend right now on each of these new
concepts is computed as: }
\han4{\it 90{\rm \%} \ of the remaining space quantum for the current task.}
\noindent \1
Heuristics for the new concept are quite hard to fill in. This was one of AM's
most serious limitations, in fact (see Chapter 7).
Above, we see a trivial kind of ``heuristic schema" or template, which gets
instantiated to provide one new, specialized heuristic about the new concept.
That new heuristic tells how to judge the interestingness of any conjecture
which crops up involving this new concept. As new conjectures get proposed,
they are evaluated by calling on a set of heuristics including this one.
Although some examples of \6F\inv -of-b\0 might be easily obtained
(or already known) at the moment of its creation, the above rule doesn't specifically
tell AM how to fill in that facet. The very last line of the heuristic indicates
that a few cpu seconds may be spent on just this sort of activity: filling in facets
of the new concept which, though not explicitly mentioned in the rule, are
easy to fill in now.
Any facet {\it f} which didn't get filled in ``right now" will
probably cause a new task to be added to the agenda, of the form: ``\6Fillin
facet {\it f} of concept {\it F\inv -of-b}\1''.
Eventually, AM would choose that task, and spend a large quantum of time working
on that single facet.
Now let's look at an instance of when this heuristic was used. At one
point, AM was working on the task ``\6Fill-in examples of
Divisors-of\0''.
This heuristic's IF-part was triggered because: Divisors-of is an
operation (from Numbers to Sets of numbers), and far more than 100 different
numbers are known, and more than 10 different sets of factors were found
altogether, and some of them were distinguished by being extreme